Từ thời kỳ phong kiến, các nhà nước ở Việt Nam đã có quan hệ ngoại giao với những quốc gia, phiên bang ngày nay thuộc Indonesia mà sử sách hay gọi là Chà Và, Tam Phật Tề. Thời nhà Trần còn ghi lại việc sứ giả Trả Oa tới diện kiến và cống nạp, ngoài ra quốc gia Champa (ngày nay là một phần của lãnh thổ Viet Nam) cũng đã có mối quan hệ bang giao thân thiết với các tiểu quốc ở Indonesia do cùng ảnh hưởng của văn minh Phật giáo tại thời điểm đó. Thời kỳ Phong kiến đã có nhiều dấu hiệu hai nước này có quan hệ với nhau từ cấp nhà nước (đi sứ), buôn bán, thậm chí là cướp bóc. Cao Bá Quát từng được triều đình Nhà Nguyễn cử sang công sứ tại Indonesia và có làm một bài thơ về người phụ nữ Tây Dương ở Indonesia. Trong thời kỳ chiến tranh Việt Nam giai đoạn 1947-1954, cả hai miền Việt Nam đã thực hiện ngoại giao để đấu tranh chính trị và đã cố gắng xây dựng quan hệ với Indonesia cũng là một nước trong khu vực.

Hai bên bắt đầu quan hệ chính thức vào ngày 30 tháng 12 năm 1955. Vào tháng 9 năm 2011, hai nước đã ký Chương trình hành động giai đoạn 2012-2015. Ngày 27 và 28 tháng 6 năm 2013, nhận lời mời của Tổng thống Susilo Bambang Yudhoyono, Chủ tịch nước Trương Tấn Sang cùng phu nhân qua thăm Indonesia nhằm khẳng định chính sách nhất quán của Việt Nam coi trọng tăng cường quan hệ hữu nghị và hợp tác với Indonesia một đối tác truyền thống và quan trọng của Việt Nam. Quan hệ Đối tác Chiến lược Việt Nam – Indonesia được ký kết.[1]